import java.util.Arrays;

public record TheNumberOfLegalTriangle() {
    public int triangleNumber(int[] nums) {
        // 有效三角形个数https://leetcode.cn/problems/valid-triangle-number/description/
        Arrays.sort(nums);
        int maxNumIndex=nums.length-1;
        int ret=0;
        for(;maxNumIndex>=2;maxNumIndex--) {
            int c=nums[maxNumIndex];
            int left=0;
            int right=maxNumIndex-1;
            while(left<right) {
                int a=nums[left];
                int b=nums[right];
                if(a+b>c) {
                    ret+=right-left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return ret;
    }
}
